/*
求最大子序列之和
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 解法1
int maxSubSum1(vector<int>& a)
{
	int n = a.size();
	int maxsum=0, cursum;
	
	// 两重循环穷举所有的连续子序列
	for (int i=0; i<n; i++) // i表示序列起始位置
	{
		for (int j=i;j<n;j++) // j表示序列结束位置
		{
			// 记录子序列的和
			cursum=0;
			for (int k=i;k<=j;k++)
				cursum += a[k];
			
			// 通过比较求最大子序列的和
			maxsum = max(maxsum, cursum);
		}
	}
	
	// 返回最大子序列之和
	return maxsum;
}

// 解法2
int maxSubSum2(vector<int>& a)
{
	int n=a.size();
	int maxsum=0, cursum;
	
	// i记录子序列起始位置
	for (int i=0; i<n; i++)
	{
		// 存储子序列之和
		cursum=0;
		
		// j记录子序列结束位置
		for (int j=i; j<n; j++)
		{
			// 更新子序列和
			cursum += a[j];
			
			// 通过比较求最大子序列之和
			maxsum=max(maxsum,cursum);
		}
	}
	
	// 返回最大子序列之和
	return maxsum;
}

// 解法3
int maxSubSum3(vector<int>& a)
{
	int n=a.size();
	int maxsum=0, cursum=0;
	
	
	for (int i=0; i<n; i++)
	{
		// 更新子序列和
		cursum += a[i];
		
		// 通过比较求最大maxsum
		maxsum = max(maxsum,cursum);
		
		// 若cursum<0，最大连续子序列从下一个位置开始 
		if(cursum<0)
			cursum=0;
	}
	
	return maxsum;
}

int main()
{
	// 初始化序列a、b
	vector<int> a={-2,11,-4,13,-5,-2};
	vector<int> b={-6,2,4,-7,5,3,2,-1,6,-9,10,-2};
	
	// 打印序列a
	printf("a: ");
	for(int i=0;i<a.size();i++)
		printf("%d ",a[i]);
	printf("\n"); 
	
	// 求序列a的最大子序列之和
	printf("  解法1：最大连续子序列的和: %d\n",maxSubSum1(a));
	printf("  解法2：最大连续子序列的和: %d\n",maxSubSum2(a));
	printf("  解法3：最大连续子序列的和: %d\n",maxSubSum3(a));

	// 打印序列b
	printf("b: ");
	for(int i=0;i<b.size();i++)
		printf("%d ",b[i]);
	printf("\n"); 
	
	// 求序列b的最大子序列之和
	printf("  解法1：最大连续子序列的和: %d\n",maxSubSum1(b));
	printf("  解法2：最大连续子序列的和: %d\n",maxSubSum2(b));
	printf("  解法3：最大连续子序列的和: %d\n",maxSubSum3(b));

	return 0;
	
}

